package answer

import "fmt"

func main() {
	target := []int{11, 16, 20, 1, 2, 13, 7, 6, 12, 3}
	arr := []int{11, 13, 3, 7, 7, 1, 10, 12, 14, 1}

	target = []int{5, 1, 3}
	arr = []int{9, 4, 2, 3, 4}
	fmt.Println(minOperations(target, arr))
}

//#link: https://leetcode-cn.com/problems/minimum-operations-to-make-a-subsequence/
func minOperations(target []int, arr []int) int {
	//1.映射target元素中对应元素的下标
	numMap := make(map[int]int)
	for index, val := range target {
		numMap[val] = index
	}
	//2.标记arr元素对应target元素中的下标
	index := make([]int, 0)
	for i := 0; i < len(arr); i++ {
		if val, ok := numMap[arr[i]]; ok {
			index = append(index, val)
		}
	}
	//3.获取最长递增子序列
	return len(target) - lengthOfLIS(index)
}

func lengthOfLIS(nums []int) int {
	pile := 0
	top := make([]int, len(nums))
	for i := 0; i < len(nums); i++ {
		num := nums[i]
		left, right := 0, pile
		for left < right {
			mid := (right-left)>>1 + left
			if num <= top[mid] {
				right = mid
			} else if num > top[mid] {
				left = mid + 1
			}
		}
		if left == pile {
			pile++
		}
		top[left] = num
	}
	return pile
}
